package com.leetcode.根据数据结构分类.并查集;

import java.util.*;

/**
 * @author: xiaomi
 * @date: 2021/1/18
 * @description: 721. 账户合并
 * https://leetcode-cn.com/problems/accounts-merge/
 */
public class B_721_账户合并 {

	public static void main(String[] args) {
		B_721_账户合并 action = new B_721_账户合并();
		List<List<String>> accounts = new ArrayList<>();
		accounts.add(Arrays.asList("John", "johnsmith@mail.com", "john00@mail.com"));
		accounts.add(Arrays.asList("John", "johnnybravo@mail.com"));
		accounts.add(Arrays.asList("John", "johnsmith@mail.com", "john_newyork@mail.com"));
		accounts.add(Arrays.asList("Mary", "mary@mail.com"));
		List<List<String>> lists = action.accountsMergeBetter(accounts);
		System.out.println("lists = " + lists);
	}

	/**
	 * 合并账号
	 * --
	 * 从题意中了解：
	 * 1.同名的不一定同人；
	 * 2.不同名一定不同人；
	 * 3.判断同人的只有一个条件：邮箱相同；但是开始时一个人可以拥有多个账号；
	 * --
	 * 算法方案：
	 * (由于邮箱默认最后通过字典排序-> TreeSet)
	 * 1.遍历一遍，组装成 HashMap(name, TreeSet)
	 * 2.遍历 HashMap 通过邮箱进行 union
	 * 3.最后通过 union find 进行输出
	 * --
	 * 太慢了。
	 *
	 * @param accounts
	 * @return
	 */
	public List<List<String>> accountsMerge(List<List<String>> accounts) {
		HashMap<Integer, TreeSet<String>> map = new HashMap<>();
		int len = accounts.size();
		for (int i = 0; i < len; i++) {
			TreeSet<String> set = new TreeSet<>();
			for (int j = 1; j < accounts.get(i).size(); j++) {
				set.add(accounts.get(i).get(j));
			}

			map.put(i, set);
		}
		InnerUnionFind unionFind = new InnerUnionFind(len);
		for (int i = 0; i < len; i++) {
			TreeSet<String> emails = map.get(i);
			for (int j = i + 1; j < len; j++) {
				TreeSet<String> treeSet = map.get(j);
				for (String item :
						emails) {
					if (treeSet.contains(item)) {
						unionFind.union(i, j);
						break;
					}
				}
			}
		}
		//最后遍历 union find
		for (int i = 0; i < len; i++) {
			unionFind.find(i);
		}
		Map<Integer, TreeSet<String>> res = new HashMap<>();
		for (int i = 0; i < len; i++) {
			int root = unionFind.parents[i];
			if (res.containsKey(root)) {
				res.get(root).addAll(map.get(i));
			} else {
				res.put(root, map.get(i));
			}
		}
		List<List<String>> resList = new ArrayList<>();
		//最后输出成答案的标准
		for (Map.Entry<Integer, TreeSet<String>> item :
				res.entrySet()) {
//            List<String> tempList = Arrays.asList(accounts.get(item.getKey()).get(0));
			List<String> tempList = new ArrayList<>();
			tempList.add(accounts.get(item.getKey()).get(0));
			for (String email :
					item.getValue()) {
				tempList.add(email);
			}
			resList.add(tempList);
		}
		return resList;
	}

	/**
	 * 对邮箱存储的结构进行优化
	 * --
	 * 看来还是不能熬夜啊，宁愿早上早点起来刷一道题！
	 * 因为思路不得劲！
	 * 怎么会想到这么笨拙的存储方式呢？？？
	 * --
	 * 应该多多逆向思考！
	 * --
	 * 使用了 emailToIndexMap 以后就快了至少一个数量级！
	 * @param accounts
	 * @return
	 */
	public List<List<String>> accountsMergeBetter(List<List<String>> accounts) {
		//存储 email - index in accounts 的映射
		HashMap<String, List<Integer>> emailToIndexMap = new HashMap<>();
		//保留之前的 tree set
		HashMap<Integer, TreeSet<String>> map = new HashMap<>();
		int len = accounts.size();
		String emailName = null;
		for (int i = 0; i < len; i++) {
			TreeSet<String> set = new TreeSet<>();
			for (int j = 1; j < accounts.get(i).size(); j++) {
				emailName = accounts.get(i).get(j);
				set.add(emailName);
				if (emailToIndexMap.containsKey(emailName)) {
                    emailToIndexMap.get(emailName).add(i);
				}else {
					List<Integer> list = new ArrayList<>();
					list.add(i);
					emailToIndexMap.put(emailName, list);
				}
			}
			map.put(i, set);
		}
		//通过 union find 进行操作
		InnerUnionFind unionFind = new InnerUnionFind(len);
		for (Map.Entry<String, List<Integer>> item:
			 emailToIndexMap.entrySet()) {
			List<Integer> list = item.getValue();
			for (int i = 1; i < list.size(); i++) {
				unionFind.union(list.get(i), list.get(0));
			}
		}
		for (int i = 0; i < len; i++) {
			unionFind.find(i);
		}
		Map<Integer, TreeSet<String>> res = new HashMap<>();
		for (int i = 0; i < len; i++) {
			int root = unionFind.parents[i];
			if (res.containsKey(root)) {
				res.get(root).addAll(map.get(i));
			} else {
				res.put(root, map.get(i));
			}
		}
		List<List<String>> resList = new ArrayList<>();
		//最后输出成答案的标准
		for (Map.Entry<Integer, TreeSet<String>> item :
				res.entrySet()) {
			List<String> tempList = new ArrayList<>();
			tempList.add(accounts.get(item.getKey()).get(0));
			for (String email :
					item.getValue()) {
				tempList.add(email);
			}
			resList.add(tempList);
		}
		return resList;
	}

	class InnerUnionFind {
		int[] parents;
		int[] ranks;

		public InnerUnionFind(int capacity) {
			parents = new int[capacity];
			ranks = new int[capacity];
			for (int i = 0; i < capacity; i++) {
				parents[i] = i;
				ranks[i] = 1;
			}
		}


		public int find(int index) {
			if (index != parents[index]) {
				parents[index] = find(parents[index]);
			}
			return parents[index];
		}

		public void union(int index1, int index2) {
			int p1 = find(index1);
			int p2 = find(index2);
			if (p1 == p2) {
				return;
			}
			if (ranks[p1] == ranks[p2]) {
				parents[p1] = parents[p2];
				ranks[p2]++;
			} else if (ranks[p1] < ranks[p2]) {
				parents[p1] = parents[p2];
			} else {
				parents[p2] = parents[p1];
			}
		}
	}
}
